package offer.zixing.chapter03;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 字符串中的所有变位词
 *
 * 输入两个字符串s1和s2，如何找出s2的所有变位词在s1中的起始下标？
 * 假设两个输入字符串中只包含英语小写字母。
 * 例如输入字符串s1为"cbadabacg"，s2为"abc"，s2有两个变位词"cba"和"bac"是s1中的字符串，
 * 输出它们在s1中的起始下标0和5。
 */
public class Test015 {
    public static void main(String[] args) {
        System.out.println(findAnagrams("aa", "bb"));
    }

    public static List<Integer> findAnagrams(String s, String p) {
        // 结构集构建
        List<Integer> list = new ArrayList<>();
        // 排除不可能存在变位词的情况
        if(s.length() < p.length()){
            return list;
        }
        // 构建字符数组
        int[] counts = new int[26];
        // s中处理p长度的字符串
        for(int i = p.length(); i < p.length(); i++){
            // 将 p 中的全部加入数组
            counts[p.charAt(i) - 'a']++;
            // 将 s 中的去掉
            counts[s.charAt(i) - 'a']--;
        }
        if(allZero(counts)){
            list.add(0);
        }
        // 处理 s.length() - p.lengh() 的字符串
        for(int j = p.length(); j < s.length(); j++){
            // 第一个指针的需要 减一 【出数组】
            counts[s.charAt(j) - 'a']--;
            // 第二个指针的需要 加一 【入数组】
            counts[s.charAt(j - p.length()) - 'a']++;
            if(allZero(counts)){
                list.add(j - p.length() + 1);
            }
        }
        return list;
    }

    private static boolean allZero(int[] counts) {
        for (int count : counts) {
            if (count != 0) {
                return false;
            }
        }
        return true;
    }
}
